/*
 * @Author: LittleSource
 * @Date: 2021-05-08 11:51:23
 * @LastEditors: LittleSource
 * @LastEditTime: 2021-05-08 13:12:24
 * @Description: 贪婪算法
 */
package greedy

import (
	"strings"
)

func greedy(needs []string, tvs map[string][]string) []string {
	result := make([]string, 0)
	for len(needs) > 0 {
		bestTv := ""    //覆盖了最多未覆盖的州的tv
		bestLength := 0 //该最佳tv覆盖了多少个未覆盖的州
		for k, v := range tvs {
			//取得v和needs交集
			coverList := intersections(v, needs)
			if len(coverList) > bestLength {
				bestTv = k
				bestLength = len(coverList)
			}
		}
		//将最优tv加入结果当中
		result = append(result, bestTv)
		//删除需要覆盖州中的当前最优州覆盖的州
		needs = delete(needs, tvs[bestTv])
	}
	return result
}

/**
 * @description: 删除arr数组中出现的target中的所有元素
 * @param {[]string} arr
 * @param {[]string} target
 * @return {*}
 */
func delete(arr, target []string) []string {
	for i := range target {
		for j := 0; j < len(arr); j++ {
			if target[i] == arr[j] {
				arr = append(arr[:j], arr[j+1:]...)
				break
			}
		}
	}
	return arr
}

/**
 * @description: 获取两个字符串数组的交集
 * @param {*} section1
 * @param {[]string} section2
 * @return {*}
 */
func intersections(section1, section2 []string) (intersection []string) {
	str1 := strings.Join(filter(section1), " ")
	for _, s := range filter(section2) {
		if strings.Contains(str1, s) {
			intersection = append(intersection, s)
		}
	}
	return
}

func filter(src []string) (res []string) {
	for _, s := range src {
		newStr := strings.Join(res, " ")
		if !strings.Contains(newStr, s) {
			res = append(res, s)
		}
	}
	return
}
